from contextlib import contextmanager
from utils.graph import digraph
from utils import debug

from cranesched.instance.activity import Activity


class PrecedenceGraph(list):
    """The precedence graph holds information about activity precedence relationships."""
    verbose = False
    
    def __init__(self, activities=()):
        list.__init__(self)
        self.id_to_activity = {}
        self.extend(activities)
        
    def __getitem__(self, key):
        if isinstance(key, int):
            return list.__getitem__(self, key)
        return self.id_to_activity[key]
        
    def append(self, activity):
        if activity.id in self.id_to_activity:
            raise Exception("duplicate activity id")
        list.append(self, activity)
        self.id_to_activity[activity.id] = activity
        
    def extend(self, activities):
        """Yeah, this looks silly but the built-in list.append does not call the append() method 
        defined in subclasses...""" 
        for activity in activities:
            self.append(activity)
            
    @property
    def arc_count(self):
        return sum(len(a.succ) for a in self)
        
    # --------------------------------------------------------------------------
    # Pre-processing functions
    def preprocess(self, verbose=None):
        """Pre-process the activity precedence graph by constraining the satisfiability windows as 
        much as possible through back- and forward-propagation of the end and start dates of each 
        activity's satisfiability window (no loss of optimality)."""
        if verbose is not None:
            self.verbose = bool(verbose)
        self._log("pre-processing precedence graph...")
        self.forward_propagate_window_starts()
        self.back_propagate_window_ends()
        self.check_windows()
        self.check_cycles()
        self._log("finished pre-processing precedence graph.")
        
    def forward_propagate_window_starts(self):
        self._propagate_window_constraint(Activity.forward_propagate_window_start,
                                          "%(activity)s: propagated to %(updated)d successors",
                                          "forward-propagating window starts...",
                                          "forward-propagation complete")
        
    def back_propagate_window_ends(self):
        self._propagate_window_constraint(Activity.back_propagate_window_end,
                                          "%(activity)s: propagated to %(updated)d predecessors",
                                          "back-propagating window ends...",
                                          "back-propagation complete")
        
    def _propagate_window_constraint(self, propagate_fnc, propagate_message, 
                                     start_message, end_message):
        """This method iterates over the precedence graph and, for each activity, it calls the 
        argument propagation function (forward- or back-propagation). Updated predecessors or 
        successors are re-added to the set of remaining activities, so the algorithm stops only 
        when propagation does not cause any more activities to be updated and there are no 
        activities in the remaining set."""
        self._log(start_message)
        remaining = set(self)
        while len(remaining) > 0:
            activity = remaining.pop()
            updated = propagate_fnc(activity)
            if len(updated) > 0:
                self._log(propagate_message % {"activity": activity.id, "updated": len(updated)})
                remaining.update(updated)
        self._log(end_message)
        
    def check_windows(self):
        """This method checks if the size of the window for each activity is greater than or equal 
        to the duration of the activity, otherwise it would not be possible to completely execute 
        the activity within its satisfiability window."""
        successes, failures = debug.try_map(Activity.check_window, self, Activity.Error)
        for activity, error in failures:
            self._log("infeasible activity: %s - %s" % (activity, error))
        if len(failures) > 0:
            raise Exception("detected %d infeasible activities" % len(failures))
            
    def check_cycles(self):
        """Checks if the given set of activities and their precedence relations represent a DAG
        (directed acyclic graph). If the graph has cycles, it means something has gone wrong with 
        the construction of the precedence graph and an exception is raised."""
        if not digraph.is_dag(self.to_plain_digraph()):
            raise Exception("precedence cycle(s) detected")
            
    # --------------------------------------------------------------------------
    # Link connection/disconnection (required for saving)
    @contextmanager
    def unlinked(self):
        self.unlink()
        yield
        self.link()
        
    def unlink(self):
        """Replace all references to predecessor and successor activities with the ids of theirs
        corresponding actions."""
        for activity in self:
            activity.unlink()
            
    def link(self):
        for activity in self:
            activity.link(self.id_to_activity)
            
    # --------------------------------------------------------------------------
    # Methods for the construction of the precedence graph        
    def setup_precedences(self):
        """Sets up precedence relationships between activities by computing the sequences of 
        actions involving the same item or the same place."""
        for sequence in self.place_sequences().itervalues():
            Activity.setup_sequence(sequence, complement=False)
        for sequence in self.item_sequences().itervalues():
            Activity.setup_sequence(sequence, complement=True)
            
    def place_sequences(self):
        """Creates a dictionary mapping place ids to the sequences of activities involving each 
        particular place."""
        sequence = {}  # {place_id: [cranesched.Activity]}
        for activity in self:
            place_id = activity.action.place
            try:
                sequence[place_id].append(activity)
            except KeyError:
                sequence[place_id] = [activity]
        return sequence
        
    def item_sequences(self):
        """Creates a dictionary mapping item ids to the sequences of activities involving each 
        particular item."""
        sequence = {}  # {item_id: [cranesched.Activity]}
        for activity in self:
            for item_id in activity.action.items:
                try:
                    sequence[item_id].append(activity)
                except KeyError:
                    sequence[item_id] = [activity]
        return sequence
        
    # --------------------------------------------------------------------------
    # Auxiliray and debugging methods
    def _log(self, message):
        if self.verbose:
            print message
            
    def pprint(self, activities=None, key=None):
        if activities is None:
            activities = self
        else:
            assert set(self).issuperset(activities)
        if key is not None:
            activities = sorted(activities, key=key)
        print object.__repr__(self)
        for activity in activities:
            pred = sorted(p.id for p in activity.pred)
            succ = sorted(s.id for s in activity.succ)
            print "%5s: %s %s" % (activity.id, pred, succ)
            
    def show(self, draw_type="spring", target=None):
        return PrecedenceGraph.show_graph(self, draw_type, target)
        
    @staticmethod
    def show_graph(activities, draw_type="spring", target=None):
        from khronos.statistics.plotter import get_plotter
        import networkx
        G = PrecedenceGraph.make_networkx_digraph(activities)
        plt = get_plotter(target)
        draw_fnc = getattr(networkx, "draw_%s" % draw_type)
        draw_fnc(G, ax=plt.active_axes)
        plt.update()
        return G, plt
        
    def to_networkx_digraph(self):
        return PrecedenceGraph.make_networkx_digraph(self)
        
    @staticmethod
    def make_networkx_digraph(activities):
        """Create a networkx digraph object from the given set of activities. Arcs from/to 
        activities outside the argument set are ignored."""
        import networkx
        G = networkx.DiGraph()
        A = set(activities)
        for a in A:
            if not G.has_node(a.id):
                G.add_node(a.id)
            for b in a.succ & A:
                G.add_edge(a.id, b.id)
        return G
        
    def to_plain_digraph(self):
        return PrecedenceGraph.make_plain_digraph(self)
        
    @staticmethod
    def make_plain_digraph(activities):
        """Return a plain and simple data structure representing the precedence graph of the 
        given set of activities. This format is suitable for use with the functions in 
        utils.graph.digraph."""
        A = set(activities)
        return {a.id: [b.id for b in a.succ & A] for a in A}
        
